package niuke;

/**
 * description:
 * author:张腾
 * date:2021-07-07
 */

import java.util.HashMap;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 */
public class NC12 {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        this.preorder = pre;
        for (int i = 0; i < in.length; i++) {
            dic.put(in[i],i);
        }
        return recur(0,0,pre.length-1);
    }
    private TreeNode recur(int root,int left,int right){
        if (left>right) return null;
        int val = preorder[root];
        TreeNode r = new TreeNode(val);
        int digit = dic.get(val);
        r.left = recur(root+1,left,digit-1);
        r.right = recur(root+digit-left+1,digit+1,right);
        return r;
    }
}
